home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group96b.txt / 000053_icon-group-sender _Wed Nov 6 20:56:32 1996.msg < prev    next >
Internet Message Format  |  1997-01-02  |  4KB
  1. Received: by cheltenham.cs.arizona.edu; Thu, 7 Nov 1996 09:34:00 MST
  2. Date: Wed, 6 Nov 1996 20:56:32 -0600
  3. Message-Id: <199611070256.UAA20251@ns1.computek.net>
  4. Mime-Version: 1.0
  5. Content-Type: text/plain
  6. Content-Transfer-Encoding: 7bit
  7. From: gep2@computek.net
  8. Subject: sets and structures
  9. To: icon-group@cs.arizona.edu
  10. X-Mailer: SPRY Mail Version: 04.00.06.17
  11. Errors-To: icon-group-errors@cs.arizona.edu
  12.  
  13. >i'm reading ``An Overview of the Icon Programming Language; Version 8''
  14. (Griswold).  the section on sets says: ``insert(S, x) has no effect if x
  15. is already in S''.
  16.  
  17. >this appears to work for atomic types eg,
  18.     procedure    main()
  19.         local    l, s
  20.         s := set()    
  21.         while(l := read()) do
  22.             insert(s, l)
  23.         every l := !s do
  24.             write(l)
  25.     end
  26.  
  27. >however, if if i try to insert a structure then it never fails,
  28.  
  29. It's not going to "fail"... storing an item into a table (or set) which is 
  30. identical to an item already in the table (or set) simply means that the one 
  31. already there which matches is effectively overwritten (in the case of a table; 
  32.  in the case of a set where there is no "data value" associated with the key, it 
  33. doesn't matter which one you want to consider is discarded, since they're both 
  34. identical).  A set can basically be thought of just like a table, except without 
  35. a specific data value corresponding to the key.
  36.  
  37. >    record    rec(a,b)
  38.     procedure    main()
  39.         local    l, s
  40.         s := set()    
  41.         while(l := read()) do {
  42.             a := l[1]
  43.             b := l[2:0]
  44.             insert(s, rec(a,b))
  45.         }
  46.         every l := !s do
  47.             write(l.a, " ", l.b)
  48.     end
  49.  
  50. >results in output like:
  51.  
  52. >; structest
  53. foo
  54. bar
  55. bar
  56. spam
  57. 
  58. b ar
  59. s pam
  60. f oo
  61. b ar
  62. ; 
  63.  
  64. >as you would expect for a list rather than a set.  so, what's the answer
  65. if you want to form a set of non-atomic types?  
  66.  
  67. You sort of need to understand SNOBOL4 where a lot of this stuff originated.  In 
  68. SNOBOL4, two variables which both contain the same string value each point to 
  69. EXACTLY the same single copy of that string.  In such a case, it's very easy to 
  70. detect identity:  if the pointers to the data descriptors that describe the two 
  71. strings are the same, then the two strings are identical.  Otherwise, they are 
  72. not.  So even two strings of thousands of characters can be "compared" for 
  73. equality by simply comparing two one-word values!
  74.  
  75. Likewise, if you set (again, in SNOBOL4, but ICON is basically the same)
  76.  
  77.        a = table()
  78.        b = a
  79.  
  80. then 'a' and 'b' point to the SAME table.  Changes to table 'a' will be 
  81. reflected in table 'b';  " ident(a,b) " would succeed.  If on the other hand you 
  82. have:
  83.  
  84.        a = table()
  85.        b = table()
  86.  
  87. then 'a' and 'b' are distinct and independent tables, whether they happen to 
  88. contain identical contents or not.  " ident(a,b) " would fail, even immediately 
  89. after the two assignment statements above (where both 'a' and 'b' are identical, 
  90. empty tables).
  91.  
  92. >do i have to do it by hand?
  93.  
  94. Yes, pretty much.  Although of course ICON and SNOBOL4 can make this relatively 
  95. easy for you, in most cases.  Clearly, if the items you want to compare are two 
  96. separately allocated arrays, (or worse, tables... which might have been created 
  97. in different chronology!) each one containing thousands of items of a variety of 
  98. data types (patterns?  code?) then clearly determining (efficiently!) if they 
  99. are really functionally identical or not (based on their present content!) could 
  100. be rather challenging, indeed!
  101.  
  102. Gordon Peterson
  103. http://www.computek.net/public/gep2/
  104.  
  105.